<?php 
/** 
 * 丑数
 * 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
  
 方法一：（时间换空间）
 从1到N遍历
 对每一个数，先一直除以2，再一直除以3，再一直除以5，知道最后商为1
 那么这个数为1，

 方法二：（空间换时间）
 对，2,3,5 进行*2，*3，*5 先计算出所有的丑数
 */

 /** 
  * 方法一
  * @param [type] $index [description]
  */
function GetUglyNumber_Solution($index)
{   
	if ($index < 0) {
		return 0;
	}
	$number = 0;
	$uglyFound = 0;

	$arr = [];

    while ($uglyFound < $index) {
    	++$number;
    	if (IsUgly($number)) {
    		++$uglyFound;
    		$arr[] = $number;
    	}
    }
    return $number;
}

function IsUgly($number)
{
	while ($number % 2 == 0) {
		$number = $number / 2;
	}
	while ($number % 3 == 0) {
		$number = $number / 3;
	}
	while ($number % 5 == 0) {
		$number = $number / 5;
	}
	return ($number == 1) ? true:false;
}



function GetUglyNumber_Solution1($index)
{
	if ($index < 0) {
		return 0;
	}

	$pUglyNumbers = [];
	$pUglyNumbers[0] = 1;
	$nextUglyIndex = 1;

	$pMultiply2 = 0;  // 代表$pMultiply2索引 在他之前的数 * 2小于当前数组的最大值，在他之后（包含他）的数 * 2大于当前数组的最大值，
	$pMultiply3 = 0;  // 代表$pMultiply3索引 在他之前的数 * 3小于当前数组的最大值，在他之后（包含他）的数 * 2大于当前数组的最大值，
	$pMultiply5 = 0;  // 代表$pMultiply5索引 在他之前的数 * 5小于当前数组的最大值，在他之后（包含他）的数 * 2大于当前数组的最大值，

	/*for ($i = 1; $i < $index ; ++$i) { 
		$pUglyNumbers[$i] = MyMin($pUglyNumbers[$pMultiply2] * 2, $pUglyNumbers[$pMultiply3] * 3, $pUglyNumbers[$pMultiply5] * 5);

		if ($pUglyNumbers[$i] == ($pUglyNumbers[$pMultiply2] * 2))
			$pMultiply2++;
		if ($pUglyNumbers[$i] == ($pUglyNumbers[$pMultiply3] * 3))
			$pMultiply3++;
		if ($pUglyNumbers[$i] == ($pUglyNumbers[$pMultiply5] * 5))
			$pMultiply5++;
	}

	return $pUglyNumbers[$index - 1];*/

	while ($nextUglyIndex < $index) {
		
		$min = MyMin($pUglyNumbers[$pMultiply2] * 2, $pUglyNumbers[$pMultiply3] * 3, $pUglyNumbers[$pMultiply5] * 5);
		$pUglyNumbers[$nextUglyIndex] = $min;

		while (($pUglyNumbers[$pMultiply2] * 2) <= $pUglyNumbers[$nextUglyIndex]) {
			++$pMultiply2;
		}
		while (($pUglyNumbers[$pMultiply3] * 3) <= $pUglyNumbers[$nextUglyIndex]) {
			++$pMultiply3;
		}
		while (($pUglyNumbers[$pMultiply5] * 5) <= $pUglyNumbers[$nextUglyIndex]) {
			++$pMultiply5;
		}

		++$nextUglyIndex;
	}
	$ugly = $pUglyNumbers[$nextUglyIndex - 1];
	return $ugly;
}

function MyMin($a, $b, $c) {
	$min = min($a, $b);
	return min($min, $c);
}


var_dump(GetUglyNumber_Solution1(100));
